<!DOCTYPE html>
<html lang="en">
	<head>
		<meta charset="UTF-8" />
		<meta http-equiv="X-UA-Compatible" content="IE=edge" />
		<meta name="viewport" content="width=device-width, initial-scale=1.0" />
		<title>单向链表的封装</title>
	</head>
	<body>
		<script>
			function LinkedList() {
				// 内部的类：节点类
				function Node(data) {
					this.data = data;
					this.next = null;
				}

				// 属性
				this.head = null;
				this.length = 0;

				// (1). append 方法
				// 在链表的末尾插入一个新节点
				LinkedList.prototype.append = function (data) {
					// 1. 创建新的节点
					let newNode = new Node(data);

					// 2. 判断是否添加的是第一个节点
					if (this.length == 0) {
						// 是第一个节点
						this.head = newNode;
					} else {
						// 找到最后一个节点
						let current = this.head;
						while (current.next) {
							current = current.next;
						}
						// 最后节点的 next 指向新的节点
						current.next = newNode;
					}
					// 3. length 加一
					this.length += 1;
				};

				// (2). toString 方法
				// 将各个节点 data 连接成字符串形式
				LinkedList.prototype.toString = function () {
					// 1. 定义变量
					let current = this.head;
					let listString = '';

					// 2. 循环获取一个个节点
					while (current) {
						listString += current.data + ' ';
						current = current.next;
					}
					return listString;
				};

				// (3). insert 方法
				// 在链表的任意位置插入新节点
				LinkedList.prototype.insert = function (position, data) {
					// 1. 先对 position 进行越界判断
					if (position < 0 || position > this.length) return false;
					// 2. 根据 data 创建 newNode
					let newNode = new Node(data);
					// 3. 判断插入的位置是否是第一个
					if (position == 0) {
						newNode = this.head.next;
						this.header = newNode;
					} else {
						// 下面的代码也包含了插入到末尾的情况
						let index = 0;
						let current = this.head;
						let previous = null;
						while (index++ < position) {
							previous = current;
							current = current.next;
						}
						newNode.next = current;
						previous.next = newNode;
					}
					// 4. length + 1
					this.length += 1;
				};

				// (4). get(position) 方法
				// 得到某个索引值节点对应的 data
				LinkedList.prototype.get = function (position) {
					// 1. 一旦涉及到 position 记得要做越界判断
					// 刚刚自己先写了，没有主要到这一点，以后要注意
					if (position < 0 || position >= this.lenth) return null;
					let index = 0;
					let current = this.head;
					while (index++ < position) {
						current = current.next;
					}
					return current.data;
				};

				// (5) indexOf(element) 方法
				// 返回指定元素的索引，如果链表中不存在此元素，则返回 -1
				LinkedList.prototype.indexOf = function (element) {
					let index = 0;
					let current = this.head;
					// 开始查找
					while (current) {
						if (current.data == element) {
							return index;
						} else {
							current = current.next;
							index++;
						}
					}
					// 最终没有找到
					return -1;
				};

				// (6) update(position, newData) 方法
				// 修改某个位置的元素
				LinkedList.prototype.update = function (position, newData) {
					// 这次看到有 position 我就想到了越界判断，看来还是要多敲才能熟练掌握
					if (position < 0 || position > this.lenth) return false;
					let index = 0;
					let current = this.head;
					while (index++ < position) {
						current = current.next;
					}
					current.data = newData;
					return true;
				};

				// (7) removeAt(position) 方法
				// 从某个特定位置移除一项, 返回删除节点的 data
				LinkedList.prototype.removeAt = function (position) {
					// 看到 position 就要进行越界判断
					if (position < 0 || position >= this.length) return null;

					let current = this.head;
					let previous = null;
					// 判断删除的是否是第一个节点
					if (position == 0) {
						this.head = this.head.next;
					} else {
						let index = 0;
						while (index++ < position) {
							previous = current;
							current = current.next;
						}
						previous.next = current.next;
					}
					this.length -= 1;
					return current.data;
					// 刚刚还在想那个删除的节点需不需要像 C 里 free 那样释放内存
					// 是不用的，浏览器会自动回收
				};

				// (8) remove(element) 方法
				// 移除一个节点
				LinkedList.prototype.remove = function (element) {
					// 1. 获取 element 在链表中的位置(索引)
					let position = this.indexOf(element);
					// 如果没有这个元素，则返回 -1 给 position，而在 removeAt 中我们做了越界判断，所以并不会有影响
					// 2. 根据位置信息，删除节点
					this.removeAt(position);
					length -= 1;
				};

				// (9) isEmpty()
				// 判断链表是否为空
				LinkedList.prototype.isEmpty = function () {
					// if (this.head == null) {
					// 	return true;
					// } else {
					// 	return false;
					// }
					// 上面的代码可以用一句代替
					return this.length == 0;
				};

				// (10) size()
				// 返回链表包含的元素个数，与数组中的 length 属性相似
				LinkedList.prototype.size = function () {
					return this.length;
				};
			}

			// 测试代码
			let list = new LinkedList();

			// 1. 测试 append
			list.append(1);
			list.append(2);
			list.append(3);
			console.log(list);

			// 2. 测试 insert
			list.insert(2, 2.5);
			console.log(list);

			// 3. 测试 get
			console.log(list.get(0));
			console.log(list.get(1));
			console.log(list.get(2));

			// 4. 测试 indexOf
			console.log(list.indexOf(3));
			console.log(list.indexOf(4));

			// 5. 测试 update
			list.update(2, 'darkgreen');
			alert(list);
			list.update(0, 'vae');
			alert(list);

			// 6. 测试 removeAt
			let removeData = list.removeAt(2);
			alert(list);
			alert(removeData);

			// 7. 测试 remove
			list.remove('vae');
			alert(list);

			// 8. 测试 isEmpty
			alert(list.isEmpty());

			// 9. 测试 size
			alert(list.size());
		</script>
	</body>
</html>
